package com.zs.letcode.path_problems_in_dynamic_programming;

/**
 * 1575. 统计所有可行路径
 * 给你一个 互不相同的整数数组，其中locations[i]表示第i个城市的位置。同时给你start，finish和fuel分别表示出发城市、目的地城市和你初始拥有的汽油总量
 * <p>
 * 每一步中，如果你在城市 i，你可以选择任意一个城市 j，满足 j != i且0 <= j < locations.length，并移动到城市j。从城市i移动到j消耗的汽油量为|locations[i] - locations[j]|，|x|表示x的绝对值。
 * <p>
 * 请注意，fuel任何时刻都不能为负，且你可以经过任意城市超过一次（包括start和finish）。
 * <p>
 * 请你返回从start到finish所有可能路径的数目。
 * <p>
 * 由于答案可能很大， 请将它对10^9 + 7取余后返回。
 * <p>
 * 示例 1：
 * <p>
 * 输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
 * 输出：4
 * 解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
 * 1 -> 3
 * 1 -> 2 -> 3
 * 1 -> 4 -> 3
 * 1 -> 4 -> 2 -> 3
 * 示例 2：
 * <p>
 * 输入：locations = [4,3,1], start = 1, finish = 0, fuel = 6
 * 输出：5
 * 解释：以下为所有可能的路径：
 * 1 -> 0，使用汽油量为 fuel = 1
 * 1 -> 2 -> 0，使用汽油量为 fuel = 5
 * 1 -> 2 -> 1 -> 0，使用汽油量为 fuel = 5
 * 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 3
 * 1 -> 0 -> 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 5
 * 示例 3：
 * <p>
 * 输入：locations = [5,2,1], start = 0, finish = 2, fuel = 3
 * 输出：0
 * 解释：没有办法只用 3 单位的汽油从 0 到达 2 。因为最短路径需要 4 单位的汽油。
 * 示例 4 ：
 * <p>
 * 输入：locations = [2,1,5], start = 0, finish = 0, fuel = 3
 * 输出：2
 * 解释：总共有两条可行路径，0 和 0 -> 1 -> 0 。
 * 示例 5：
 * <p>
 * 输入：locations = [1,2,3], start = 0, finish = 2, fuel = 40
 * 输出：615088286
 * 解释：路径总数为 2615088300 。将结果对 10^9 + 7 取余，得到 615088286 。
 * <p>
 * 提示：
 * <p>
 * 2 <= locations.length <= 100
 * 1 <= locations[i] <= 10^9
 * 所有locations中的整数 互不相同。
 * 0 <= start, finish <locations.length
 * 1 <= fuel <= 200
 * 相关标签
 * 记忆化搜索
 * 数组
 * 动态规划
 * <p>
 * 作者：宫水三叶
 * 链接：https://leetcode-cn.com/leetbook/read/path-problems-in-dynamic-programming/r82ix6/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/11/2 13:08
 */
public class Chapter8 {
    public static void main(String[] args) {

    }

    private class Solution {
        int mod = 1000000007;

        public int countRoutes(int[] ls, int start, int end, int fuel) {
            int n = ls.length;

            // f[i][j] 代表从位置 i 出发，当前油量为 j 时，到达目的地的路径数
            int[][] f = new int[n][fuel + 1];

            // 对于本身位置就在目的地的状态，路径数为 1
            for (int i = 0; i <= fuel; i++) {
                f[end][i] = 1;
            }

            // 从状态转移方程可以发现 f[i][fuel]=f[i][fuel]+f[k][fuel-need]
            // 在计算 f[i][fuel] 的时候依赖于 f[k][fuel-need]
            // 其中 i 和 k 并无严格的大小关系
            // 而 fuel 和 fuel-need 具有严格大小关系：fuel >= fuel-need
            // 因此需要先从小到大枚举油量
            for (int cur = 0; cur <= fuel; cur++) {
                for (int i = 0; i < n; i++) {
                    for (int k = 0; k < n; k++) {
                        if (i != k) {
                            int need = Math.abs(ls[i] - ls[k]);
                            if (cur >= need) {
                                f[i][cur] += f[k][cur - need];
                                f[i][cur] %= mod;
                            }
                        }
                    }
                }
            }
            return f[start][fuel];
        }
    }
}
